home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / graycd.zip / GRAYCD.C < prev   
C/C++ Source or Header  |  1992-01-26  |  3KB  |  126 lines
  1. /*  generate Gray code for a bit string NrBits in length
  2.  
  3.     Gray code is a binary numbering system in which successive bit patterns
  4.     differ in only one bit.  Useful for shaft encoding and other applications
  5.     where we might be off a bit (pun intended). 
  6.  
  7.       for example, the command:
  8.         graycd 3
  9.       would generate the following eight lines showing the line number,
  10.         along with the decimal and binary values of the Gray code.
  11.             1   0    0 0 0         5   6    1 1 0
  12.             2   1    0 0 1         6   7    1 1 1
  13.             3   3    0 1 1         7   5    1 0 1
  14.             4   2    0 1 0         8   4    1 0 0
  15.  
  16.      w.howell (cis 70215,206)  1/24/92
  17.  
  18.      define K_R to compile under BSD4.3 (ie. cc -DK_R graycd.c)
  19.      define DEBUG to include Gray code check in bitprint routine
  20.  
  21.      tested under MicroSoft C6.0, Borland C++ 1.0, as well as
  22.        under BSD4.3 and SCO UNIX V (an other MicroSoft C).
  23.  */
  24.  
  25. #include <stdio.h>
  26.  
  27. #define MAX  14
  28.  
  29. #ifdef K_R
  30. void main( );
  31. void gray( );
  32. void bitprint( );
  33. void usage( );
  34. #else
  35. void main( int, char * * );
  36. void gray( int );
  37. void bitprint( void );
  38. void usage( void );
  39. #endif
  40.  
  41. int NrBits, Value = 0;
  42.  
  43. void main( argc, argv)
  44. int argc;
  45. char **argv;
  46. {
  47.     int main_mask;
  48.  
  49.     /* get the command line arg of number of bits */
  50.     if(argc < 2) usage();
  51.  
  52.     NrBits = atoi(argv[1]);
  53.     if(NrBits < 2 | NrBits > MAX) {
  54.       fprintf(stderr,"NrBits = %d outside the range of 2 to %d\n", NrBits, MAX);
  55.       usage();
  56.       }
  57.  
  58.     /* now let's do it */
  59.     main_mask = (1 << (NrBits - 1) );
  60.     gray(main_mask);
  61. }
  62.  
  63. /* recursively print gray code until mask = 0  */
  64. void gray( mask )
  65. int mask;
  66. {
  67.     int new_mask;
  68.  
  69.     new_mask = mask >> 1;
  70.  
  71.     if(new_mask) {
  72.       gray(new_mask);
  73.       Value = Value ^ mask;
  74.       gray(new_mask);
  75.       } 
  76.     else {
  77.       bitprint();
  78.       Value = Value ^ mask;
  79.       bitprint();
  80.       }
  81. }
  82.  
  83. #ifdef K_R
  84. void bitprint( )
  85. #else
  86. void bitprint(void)
  87. #endif
  88. {
  89. #ifdef DEBUG
  90.     static int last = 1;  /* start with 1 because first is 0 */
  91.     int  test = 0, bitcount = 0;
  92. #endif
  93.     static int count = 0;
  94.     int i, bit_mask = (1 << (NrBits - 1) );
  95.  
  96.     count++;
  97.     printf("%3d %3d   ", count, Value);
  98.  
  99.     for(i=0; i<NrBits; i++, bit_mask = bit_mask >> 1) {
  100.        if(Value & bit_mask) printf(" 1");
  101.        else                 printf(" 0");
  102.        }
  103.     printf("\n");
  104.  
  105. #ifdef DEBUG
  106.       /* count the number of bits changed -- BETTER BE ONLY 1 if gray */
  107.     test = last ^ Value;
  108.     for(; test;  test = test >> 1) if(test & 0x0001) bitcount++;
  109.     if(bitcount != 1) {
  110.        fprintf(stderr,"%d Changes from %d to %d\n", bitcount, last, Value);
  111.        usage();
  112.        }
  113.     last = Value;
  114. #endif
  115. }
  116.  
  117. #ifdef K_R
  118. void usage()
  119. #else
  120. void usage(void)
  121. #endif
  122. {
  123. fprintf(stderr, "\nUSAGE:  graycd nr_bits\n\n");
  124. exit(4);
  125. }
  126.